package DataStructure_ZL.二叉树.实现二叉树基本操作;

import java.util.*;


//用前序中序后序遍二历叉树
public class BinaryTree {
    public static int size = -1;//节点数
    public static int leafSize = -1;//叶子节点数

    public static class TreeNode {
        public char val;
        public TreeNode right;
        public TreeNode left;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //创建二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val);
        inOrder(root.right);
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val);
    }

    // 获取树中节点的个数
    int size(TreeNode root) {
        if (root == null) return 0;
        size++;
        size(root.left);
        size(root.right);

        return size + 1;
    }

    // 获取叶子节点的个数，返回的leafsize+1是因为定义的时候定义的是等于-1。
    int getLeafTreeNodeCount(TreeNode root) {
        if (root == null) return 0;
        getLeafTreeNodeCount(root.left);
        getLeafTreeNodeCount(root.right);
        if (root.left == null && root.right == null) leafSize++;
        return leafSize+1 ;
    }

    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    int getKLevelTreeNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return getKLevelTreeNodeCount(root.left, k - 1) +
                getKLevelTreeNodeCount(root.right, k - 1);
    }

    // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if (root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left > right ? left + 1 : right + 1;
    }

    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode left = find(root.left, val);
        if (left != null) return left;
        TreeNode right = find(root.right, val);
        if (right != null) return right;
        return null;
    }

    //层序遍历
    void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);

        while (!qu.isEmpty()) {
            TreeNode cur = qu.poll();
            System.out.println(cur.val + " ");
            if (cur.left != null) {
                qu.offer(cur.left);
            }
            if (cur.right != null) {
                qu.offer(cur.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) return false;
        }
        return true;
    }

    //判断两个二叉树是否相同
    boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (!isSameTree(p.left, q.left) || !isSameTree(p.right, q.right)) {
            return false;
        } else {
            return p.val == q.val;
        }
    }

    /*
    给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和
    节点值的子树。如果存在，返回 true ；否则，返回 false 。
    二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所
    有后代节点。tree 也可以看做它自身的一棵子树。。
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (isSameTree(root, subRoot)) return true;
        if (isSubtree(root.left, subRoot)) return true;
        if (isSubtree(root.right, subRoot)) return true;
        return false;
    }

    /*
    给定一个二叉树，判断它是否是高度平衡的二叉树。
    本题中，一棵高度平衡二叉树定义为：
    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
    时间复杂度为O（n^2）不是最优解，还有其他的解法
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return isBalanced(root.left) && isBalanced(root.right)
                && Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1;
    }

    /*
    给你一个二叉树的根节点 root ， 检查它是否轴对称
     */
    public boolean isChild(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isChild(left.left, right.right) && isChild(left.right, right.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isChild(root.left, root.right);
    }

    /*
    编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
     例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
     建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
     */
    //以前序创建一个二叉树str是指输入的二叉树字符串
    int i = 0;

    public TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        } else {
            i++;
        }
        return root;
    }

    /*
    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点
p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖
先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        if (left != null) return left;
        if (right != null) return right;
        return null;
    }

    /*
    输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
     */
    TreeNode prev = null;

    public void ConvertChild(TreeNode cur) {
        if (cur == null) return;
        ConvertChild(cur.left);
        cur.left = prev;
        if (prev != null) prev.right = cur;
        prev = cur;
        ConvertChild(cur.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        ConvertChild(pRootOfTree);
        TreeNode head = pRootOfTree;
        while (head.left != null) head = head.left;
        return head;
    }

    //用一个方法解决
    /*
    TreeNode head=null;
    TreeNode prev=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)return null;
        Convert(pRootOfTree.left);
            if(prev==null){
                head=pRootOfTree;
                prev=pRootOfTree;
            }else{
                prev.right=pRootOfTree;
                pRootOfTree.left=prev;
                prev=pRootOfTree;
            }
        Convert(pRootOfTree.right);
        return head;
    }
     */
/*
给定两个整数数组preorder 和 inorder，其中preorder 是二叉树的先序遍历，
inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
    //proIndex是中间的根节点索引begin是起始索引end的是结束索引
   /* public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildChild(preorder,inorder,0,inorder.length-1);
    }
    int proIndex=0;
    public TreeNode buildChild(int[] preorder,int[] inorder,int begin,int end){
        if (begin>end)return null;
        TreeNode root=new TreeNode(preorder[proIndex]);
        int rootIndex=findIndex(inorder,begin,end,preorder[proIndex]);
        proIndex++;
        root.left=buildChild(preorder,inorder,begin,rootIndex-1);
        root.right=buildChild(preorder,inorder,rootIndex+1,end);
        return root;
    }
    private int findIndex(int[] inorder,int begin,int end,int val){
        for (int i=begin;i<=end;i++){
            if (inorder[i]==val){
                return i;
            }
        }
        return -1;//没有该值
    }

    */
/*
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为
一个由括号和整数组成的字符串，返回构造出的字符串。
https://leetcode.cn/problems/construct-string-from-binary-tree/
 */
    public void stringBuilder(StringBuilder sbd, TreeNode root) {
        if (root == null) return;
        sbd.append(root.val);
        if (root.left != null) {
            sbd.append('(');
            stringBuilder(sbd, root.left);
            sbd.append(')');
        } else {
            if (root.right == null) {
                return;
            } else {
                sbd.append("()");
            }
        }
        if (root.right == null) {
            return;
        } else {
            sbd.append('(');
            stringBuilder(sbd, root.right);
            sbd.append(')');
        }

    }

    public String tree2str(TreeNode root) {
        if (root == null) return null;
        StringBuilder sbd = new StringBuilder();
        stringBuilder(sbd, root);
        return sbd.toString();
    }

    /*
    给你二叉树的根节点 root ，返回它节点值的 前序 遍历(非递归).
     */
    /*
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }
     */

    //测试
    public static void main(String[] args) {
        BinaryTree ou = new BinaryTree();
        BinaryTree.TreeNode iu = ou.createTree();
//        iu.postOrder(iu.createTree());
//        System.out.println(ou.size(iu));
//        System.out.println(ou.getLeafTreeNodeCount(iu));
//        System.out.println(ou.getKLevelTreeNodeCount(iu,45));
//        System.out.println(ou.getHeight(iu));
//        System.out.println(ou.find(iu, 'D'));
//          ou.levelOrder(iu);
        System.out.println(ou.isCompleteTree(iu));

    }
}
